package com.cuz.daileetcode;

public class Day33_1 {

    private static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
    }


    public static TreeNode getSuccessor(TreeNode node) {
        if (node == null) {
            return null;
        }
        //Node 存在右孩子 ，那么右孩子的最左节点是它的后继节点
        if (node.right != null) {
            TreeNode temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            return temp;
        } else {
            //如果不存在右孩子
            //1.node是某一个节点A的左孩子 那么返回这个节点A
            //2.node是某一个节点的右孩子 一直向上找一个节点C
            //C需要满足是C的左树上存在节点node 返回c，
            //如果一直找不到 说明 node是这个树的最右节点返回null
            TreeNode parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }
}
